package leetcode_1000;

/**
 * @author 周杨
 * 2018年11月20日 下午9:06:23 给定一个N 要求N的一个全排列 所有i<k<j 不能出现A[k]*2=A[i]+A[j]
 * BeautifulArray_932.java
 * description:用分治思想 把数组分开处理 AC 70%
 * see:https://blog.csdn.net/Dylan_Frank/article/details/83504983
 */
public class BeautifulArray_932 {
	public int[] beautifulArray(int N) {
        if(N==1) return new int[] {1};
        if(N==2) return new int[] {2,1};
        int []res=new int[N];
        int mid=N/2;
        int right=mid;
        if((N&1)==1) {//如果N是奇数
        	res[mid]=1;//1分配在最中间
        	right=mid+1;
        }
        int[]left=beautifulArray(mid);//此时显然是左半区间的填充
        for(int i=0;i<left.length;++i) res[i]=left[i]<<1;//左数组不停左位移
        if(right>mid) {//如果是奇数
        	for(int i=0;i<left.length;++i) res[right+i]=left[i]*2+1;
        }
        else {
        	for(int i=0;i<left.length;++i) res[right+i]=left[i]*2-1;
        }
        return res;
    }
}
